Lấp kín đường cụt Thuật toán tìm đường đi trong mê cung

Lấp kín đường cụt (dead-end filling) là một thuật toán để giải mê cung bằng cách lấp kín tất cả các ngã cụt, chỉ để lại một đường chính xác không bị lấp. Nó có thể được sử dụng để giải các mê cung trên giấy hoặc với một chương trình máy tính, nhưng nó không hữu dụng nếu mê cung chưa biết bởi vì phương pháp này phải biết trước toàn bộ bộ mê cung. Các bước của phương pháp lấp kín đường cụt là:

  1. Tìm tất cả điểm cụt trong mê cung
  2. "Lấp kín" các con đường từ mỗi điểm cụt cho đến ngã giao đầu tiên.

Xem đoạn phim mô phỏng giải thuật này tại: .

Tài liệu tham khảo

WikiPedia: Thuật toán tìm đường đi trong mê cung http://books.google.com/books?id=m3QTSMYm5rkC&pg=P... http://www.mazeworks.com/mazegen/ http://www.youtube.com/watch?v=FkueaIT6RSU&NR=1 http://www.youtube.com/watch?v=jhL8uELbVIM http://www.youtube.com/watch?v=yqZDYcpCGAI http://www.astrolog.org/labyrnth/algrithm.htm#solv... http://www.cb.uu.se/~cris/blog/index.php/archives/... https://www.youtube.com/watch?v=IIBwiGrUgzc https://www.youtube.com/watch?v=k1tSK5V1pds